package com.sicheng.lc.周赛.分类.模拟;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/23 14:45
 */
public class 买钢笔和铅笔的方案数 {
    //https://leetcode.cn/problems/number-of-ways-to-buy-pens-and-pencils/
    public long waysToBuyPensPencils(int total, int cost1, int cost2) {
        //大致思路就是
        // 因为题目算种数， 全部买cost1 最多可以买 total/cost1 最少买1件cost1.总数就是total/cost1
        // 所有的钱买cost1 , 再买一件cost2
        // 剩下的钱重复上一步
        long res = 0;
        while (total >= 0) {
            res += total / cost1 + 1;
            total -= cost2;
        }
        return res;
    }

    // 时间 O(n)  空间O(n)
    private long dp(int total, int cost1, int cost2) {
        if (total < Math.min(cost1, cost2))
            return 1;
        if (total == Math.min(cost1, cost2))
            return 2;
        long[] dp = new long[total + 1];
        dp[0] = 0;
        for (int i = cost1; i <= total; i++) {
            dp[i] += dp[i - cost1] + 1;
        }
        for (int i = cost2; i <= total; i++) {
            dp[i] += dp[i - cost2] + 1;
        }

        return dp[total] + 1;
    }


    public static void main(String[] args) {
        买钢笔和铅笔的方案数 solution = new 买钢笔和铅笔的方案数();
        System.out.println(solution.waysToBuyPensPencils(20, 5, 10));
    }
}
